package com.aqie.easy.backtrackingAlgorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 784 字母大小写全排列
 * DFS  回溯法
 * todo
 */
public class LetterCasePermutation {
    /**
     * 用dfs实现回溯，start代表目前从扫描到第几位，
     *
     * 如果是digit，就直接加进去，然后下一层递归
     *
     * 如果是alpha，就先加进去，然后下一层递归；再加对立大小写形式， 然后下一层递归。
     */
    List<String> ans = new ArrayList<>();
    public List<String> letterCasePermutation(String S) {
        dfs(new StringBuilder(S), 0);
        return null;
    }

    private void dfs(StringBuilder s, int cur) {
        if (cur == s.length()){
            ans.add(s.toString());
            return;
        }
        if (Character.isDigit(s.charAt(cur))){
            dfs(s, cur + 1);
        }else {
            char ch = s.charAt(cur);
            s.setCharAt(cur,Character.toLowerCase(ch));
            dfs(s,cur + 1);
            s.setCharAt(cur,Character.toUpperCase(ch));
            dfs(s,cur + 1);

        }
    }
}
